package 力扣日常刷题.木22一月.第17天0129;

import java.util.ArrayDeque;

/**
 * @author 帅小伙
 * @date 2022/1/29
 * @description
 */
public class Demo27中等多源BFS地图上的最高点 {


    public int[][] highestPeak(int[][] g) {
        int m = g.length, n = g[0].length;
        int[][] ans = new int[m][n];
        ArrayDeque<int[]> d = new ArrayDeque<>();
        // 为所有可以成为陆地的地方赋成-1  并且加入所有的虚节点
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (g[i][j] == 1) d.add(new int[]{i, j});
                ans[i][j] = g[i][j] == 1 ? 0 : -1;
            }
        }
        int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!d.isEmpty()) {
            int[] info = d.pollFirst();
            int x = info[0], y = info[1];
            for (int[] dir : dirs) {
                int nx = x + dir[0], ny = y + dir[1];
                if(nx<0||nx>=m|| ny<0||ny>=n) continue;
                if(ans[nx][ny] != -1)continue;
                ans[nx][ny] = ans[x][y] + 1;
                d.addLast(new int[]{nx,ny});
            }
        }
        return ans;
    }
}
